package binary

import "math"

func Add(a, b int) int {
	sum := a
	for b != 0 {
		sum = a ^ b
		b = (a&b) << 1
		a = sum
	}
	return sum
}

func Minus(a, b int) int {
	return Add(a, Opposite(b))
}

func Opposite(a int) int {
	return Add(^a, 1)
}

func Multiply(a, b int) int {
	var isBNeg bool
	if isNeg(b) {
		isBNeg = true
		b = Opposite(b)
	}
	ans := 0
	for b!=0 {
		if b&1 != 0 {
			ans = Add(ans, a)
		}
		a <<= 1
		b >>= 1
	}
	if isBNeg {
		return Opposite(ans)
	}
	return ans
}

func isNeg(a int) bool {
	if a < 0 {return true}
	return false
}

func Divide(dividend, divisor int) int {
	if divisor == math.MinInt32 {
		return 0
	} else if dividend == math.MinInt32 {
		if divisor == Opposite(1) {
			return math.MaxInt32
		}
		ans := Div(Add(dividend, 1), divisor)
		return Add(ans, Div(Minus(dividend, Multiply(ans, divisor)), divisor))
	}
	return Div(dividend, divisor)
}

func Div(a, b int) int {
	var x, y, ans int
	if isNeg(a) {
		x = Opposite(a)
	} else {
		x = a
	}
	if isNeg(b) {
		y = Opposite(b)
	} else {
		y = b
	}
	for i:=62; i>=0; i=Minus(i,1) {
		if (x>>i) >= y{
			ans |= 1<<i
			x = Minus(x, y<<i)
		}
	}
	if isNeg(b) == isNeg(a) {
		return ans
	}
	return Opposite(ans)
}